package com.zhugang.week10;

/**
 * @program algorithms
 * @description: findTargetSumWays
 * @author: chanzhugang
 * @create: 2022/08/29 14:10
 */
public class FindTargetSumWays {

    /**
     * 494 目标和
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        // nums数字前添加 '+' 或 '-',构成表达式的和 == target， 有多少种不同表达式
        // 抽象为0-1背包问题，所装物品总重target，有多少种装法
        // dp[i][j]: 第i个决策物品重量为j这种状态有多少种方法
        // dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][ j + nums[i]]
        if (target > 1000 || target < -1000) {
            return 0;
        }
        int n = nums.length;
        // 为什么要设置偏移量(越界)? 比如称东西，可以把东西放在盒子里称，最后减掉盒子的重量类似
        int offset = 1000;
        int w = 2000;
        int[][] dp = new int[n][w + 1];

        // 初始化
        dp[0][offset - nums[0]] += 1;
        dp[0][offset + nums[0]] += 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (j - nums[i] >= 0 && j - nums[i] <= w) {
                    // "+"
                    dp[i][j] = dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] >= 0 && j + nums[i] <= w) {
                    // "-"
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
            }
        }
        return dp[n - 1][target + offset];
    }
}